#!/usr/bin/env python3

"""
Given an unsorted integer array, find the smallest missing positive integer.

Example 1: 
Input: [1, 2, 0]
Output: 3

Example 2:
Input: [3, 4, -1, 1]
Output: 2

Example 3:
Input: [7, 8, 9, 11, 12]
Output: 1

Note:
your algorithm should run in O(n) time and uses constant extra space.
"""

"""
# 使用递归
class Solution:
    def find_missing_positive(self, nums):
        if len(nums) == 0:
            return 1
        return self._find_missing_positive(nums, 0, 1)

    def _find_missing_positive(self, nums, start, cur_smallest):
        if len(nums) == start:
            return cur_smallest
        current = nums[start]
        if cur_smallest == current:
            result = self._find_missing_positive(nums, start + 1, current + 1)
        else:
            result = cur_smallest
        result = self._find_missing_positive(nums, start + 1, result)
        if result == current:
            result = self._find_missing_positive(nums, start + 1, current + 1)
        return result
"""

class Solution:
    """ [1, n + 1] 区间内, 坐标最终结果+1 """
    def find_missing_positive(self, nums):
        n = len(nums)
        for index, val in enumerate(nums):
            while val <= n and val > 0 and index + 1 != val and nums[val - 1] != val:
                nums[index], nums[val - 1] = nums[val - 1], nums[index]
                val = nums[index]
            if index + 1 != val:
                nums[index] = 0
        for index, val in enumerate(nums):
            if val == 0:
                return index + 1
        else:
            return n + 1

if __name__ == '__main__':
    solution = Solution()
    assert 5 == solution.find_missing_positive([1, 2, 2, 1, 3, 1, 0, 4, 0])
    assert 3 == solution.find_missing_positive([2, 1])
    assert 3 == solution.find_missing_positive([1, 2, 0])
    assert 2 == solution.find_missing_positive([3, 4, -1, 1])
    assert 1 == solution.find_missing_positive([7, 8, 9, 11, 12])
    
